/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode node1 = head;
        ListNode lastnode = head;
        // flag = node1;
        //1.为首节点
        //2.不为首节点
        while(node1 != null ){
            if(node1.val ==val && node1 == head){
                node1 = node1.next;
                head = node1;
                continue;
            }
            if(node1.val == val){
                lastnode.next = node1.next;
                node1 = node1.next;
            }
            else{
                lastnode = node1;
                node1 = node1.next;
            }
            
        }
    return head;
    }
}

// 虚拟头节点法
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 创建虚拟头节点，简化边界处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        
        // prev指向当前节点的前一个节点
        ListNode prev = dummyHead;
        // current指向当前正在检查的节点
        ListNode current = head;
        
        while (current != null) {
            if (current.val == val) {
                // 删除当前节点：让前一个节点直接指向下一个节点
                prev.next = current.next;
            } else {
                // 不删除：prev向前移动
                prev = current;
            }
            // current总是向前移动
            current = current.next;
        }
        
        // 返回真正的头节点
        return dummyHead.next;
    }
}


// 递归法
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 递归终止条件
        if (head == null) {
            return null;
        }
        
        // 递归处理后面的节点
        head.next = removeElements(head.next, val);
        
        // 判断当前节点是否需要删除
        return head.val == val ? head.next : head;
    }
}